package algorithmic_data_structure.暴力递归;

import org.junit.Test;

import java.util.Stack;

//不能使用额外空间(使用的是虚拟机栈)
public class 逆序栈 {

    public void reverseStack(Stack<Integer> stack){
        int i = getLastStackNum(stack); //栈底元素，先存在jvm栈中
        if (!stack.isEmpty()){
            reverseStack(stack);    //取出栈底元素后，剩余元素reverse
        }
        stack.push(i);          //在已经reverse的栈 压入一开始取出的栈底元素
    }
    //拿出栈底元素，其他顺序不变
    //把这个方法看作黑盒
    public int getLastStackNum(Stack<Integer> stack){
        int i = stack.pop();//利用jvm中的栈 存着先
        if (stack.isEmpty()){
            return i;
        }
        //取出栈底元素 其他不变
        int lastStackNum = getLastStackNum(stack);
        stack.push(i);
        return lastStackNum;
    }
    @Test
    public void test2(){
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        reverseStack(stack);
        /*
        栈初始状态：
            5
            4
            3
            2
            1
         */
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
    @Test
    public void test(){
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        /*
        栈初始状态：
            5
            4
            3
            2
            1
         */
        while (!stack.isEmpty()){
            System.out.println(getLastStackNum(stack));
        }
    }

}
